Disjoint Sparse Table
Operations
半群の列 $ (a_0, a_1, \dots, a_{n - 1}) を扱う．
空間計算量$ \Theta(n \log n)
$ \mathtt{build}(a_0, a_1, \dots, a_{n - 1})
与えられた列を表現する Disjoint Sparse Table を作成する
時間計算量$ \Theta(n \log n)
$ \mathtt{fold}(l, r)
$ a_l \cdot a_{l + 1} \cdot \dots \cdot a_r を計算する
時間計算量$ \Theta(1)
Summary
https://gyazo.com/d403537b51cc94912252fa1399d22e6b
長さ$ 2以上のすべての区間がちょうど二つに分割されるように，累積和のテーブルを構築する
References
Notes
Implementations
Problems